package algorithm;

public class leetcode_0322 {
    public int coinChange(int[] coins, int amount) {
        int len=coins.length;
        int[] dp=new int[amount+1];
        for(int i=1;i<=amount;++i){
            dp[i]=100000;
        }
        for(int i=1;i<=amount;++i){
            for(int j=0;j<len;++j){
                if(i>=coins[j]){
                    dp[i]=Math.min(dp[i],dp[i-coins[j]]+1);
                }
            }
        }
        if(dp[amount]==100000) return -1;
        return dp[amount];
    }
}
